package leetcode._397;

/**
 * Given a positive integer n and you can do operations as follow:
 * If n is even, replace n with n/2.
 * If n is odd, you can replace n with either n + 1 or n - 1.
 * What is the minimum number of replacements needed for n to become 1?
 * @author yachao
 *
 */

public class IntegerReplace {
	
	public int integerReplace(int n) {
		if (n == Integer.MAX_VALUE) {
			return 32;
		}
		
		int count = 0;
		while (n > 1) {
			if ((n & 1) == 0) {
				n = n >> 1;
				count++;
			} else {
				if (n == 3) {
					n = 2;
				} else {
					if (countTrailZero(n - 1) > countTrailZero(n + 1)) {
						n = n - 1;
					} else {
						n = n + 1;
					}
				}
				count++;
			}
		}
		
		return count;
	}

	public int countTrailZero(int n) {
		int count = 0;
		
		while ((n & 1) == 0) {
			n = n >> 1;
			count++;
		}
		return count;
	}
	
	public static void main(String[] args) {
		System.out.println(new IntegerReplace().integerReplace(3));
	}
}
